﻿#include <iostream>

using namespace std;

/*
Do permution for the string through non-recursive algorithm, 
assume the string does not contain duplicate character.
for example:
Input: abcd
Output: abcd bacd cabd dabc
        abdc badc cadb dacb
		acbd bcad cbad dbac
		acdb bcda cbda dbca
		adbc bdac cdab dcab
		adcb bdca cdba dcba
*/

/*
Permutation iteration algorithm:
1. Search from the end of the array a[], find the first index x1 to meet a[x1]<a[x1+1]
2. Search from the end of the array a[], find the first index x2 to meet a[x1]<a[x2]
3. swap a[x1],a[x2] and revert all elements between a[x1+1] and a[end] (inclusive)
*/

template<class T>
void swap1( T &x, T &y)
{
	T temp = x;
	x = y;
	y = temp;
}

template<class T>
void Revert( T *arr, int start, int end)
{
	while( start<end )
	{
		T tmp = arr[start];
		arr[start] = arr[end];
		arr[end] = tmp;
		start++;
		end--;
	}
}

int FindFirstX1(int *index, int len)
{
	for( int i=len-1; i>=0; i--)
	{
		if(index[i]<index[i+1])
			return i;
	}
	return -1;
}

int FindFirstX2(int *index, int len, int x1)
{
	for(int i=len-1; i>=0; i--)
	{
		if(index[i]>index[x1])
			return i;
	}
	return -1;
}

/*
do the iterative permutation
*/
void PermuteEasy( char* str)
{
	int len = strlen(str);
	int *index = new int[len];
	int totalCount = 0;

	for( int i=0;i<len; i++)
	{
		index[i]=i;
	}

	char *outPut = new char[len+1];
	outPut[len] = '\0';
	memcpy(outPut, str, len);
	cout<<outPut<<endl;
	totalCount++;

	while(1)
	{
		int x1=FindFirstX1(index, len);
		if( x1<0)
		{
			// finish permutation
			break;
		}
		int x2=FindFirstX2(index, len, x1);
		swap1(index[x1], index[x2]);
		swap1(outPut[x1], outPut[x2]);
		Revert(index, x1+1, len-1);
		Revert(outPut, x1+1, len-1);
		cout<<outPut<<endl;
		totalCount++;
	}
	
	cout<<"total count is "<<totalCount<<endl;
}

/*
do the permutation next. it is used for permutation iterator.
*/
bool PermutationNext( int *IndexArray, int Len)
{
	int x1=FindFirstX1(IndexArray, Len);
	if( x1<0)
	{
		// finish permutation
		return false;
	}

	int x2=FindFirstX2(IndexArray, Len, x1);
	swap1(IndexArray[x1], IndexArray[x2]);
	Revert(IndexArray, x1+1, Len-1);
	return true;
}

void PermutationThroughNext( char* str )
{
	int len = strlen(str);
	int *index = new int[len];
	int totalCount = 0;

	for( int i=0;i<len; i++)
	{
		index[i]=i;
	}

	char *outPut = new char[len+1];
	outPut[len] = '\0';
	memcpy(outPut, str, len);
	cout<<outPut<<endl;
	totalCount++;

	while( PermutationNext(index, len) )
	{
		for( int i=0; i<len; i++ )
		{
			outPut[i] = str[index[i]];
		}
		cout<<outPut<<endl;
		totalCount++;
	}

	cout<<"total count is "<<totalCount<<endl;
}

int main()
{
	char str[] = "1234";

	PermuteEasy(str);
	cout<<"PermutationEasy end\n"<<endl;	

	PermutationThroughNext(str);
	cout<<"PermutationThroughNext end\n"<<endl;

	cout<<"Press any key to terminate..."<<endl;

	return getchar();
}